package com.mzy.interview

import java.util.PriorityQueue

/**
 * @Author: mizy3
 * @Date: 2024/08/25/下午2:34
 * @Description:
 */
class 合并K个升序链表 {

    fun mergeKLists(lists: Array<ListNode?>): ListNode? {
        val pq = PriorityQueue<ListNode> { a, b -> a.`val` - b.`val` }
        for (list in lists) {
            if(list != null)
                pq.offer(list)
        }

        var dummy : ListNode? = ListNode(-1, null)
        var ans: ListNode? = dummy
        while (!pq.isEmpty()) {
            val node = pq.poll()
            if (node.next != null) {
                pq.offer(node.next)
            }
            dummy?.next = node
            dummy = dummy?.next

        }

        return ans?.next
    }
}

fun main() {
    val mutableListOf = mutableListOf(ListNode(1), ListNode(2))
    合并K个升序链表().mergeKLists(mutableListOf.toTypedArray())
}